package com.cdream.basic.algorithm.leetcode.dfs;

/**
 * @author cdream
 * @date 2022/2/24
 */
public class Question1706 {
    public static void main(String[] args) {
        new Question1706().findBall(
                new int[][]{
                        {1,1,1,-1,-1},
                        {1,1,1,-1,-1},
                        {-1,-1,-1,1,1},
                        {1,1,1,1,-1},
                        {-1,-1,-1,-1,-1}
                }
        );
    }
    int rlen, clen;

    public int[] findBall(int[][] grid) {
        rlen = grid.length;
        clen = grid[0].length;
        int[] res = new int[clen];
        for (int j = 0; j < clen; j++) {
            int k = dfs(grid, 0, j);
            res[j] = k;
        }
        return res;
    }

    int dfs(int[][] arr, int i, int j) {
        if (i >= rlen) {
            return j;
        }
        if (arr[i][j] == 1) {
            if (j == clen - 1 || arr[i][j + 1] == -1) {
                return -1;
            }
            return dfs(arr, i + 1, j + 1);
        }
        if (arr[i][j] == -1) {
            if (j == 0 || arr[i][j - 1] == 1) {
                return -1;
            }
            return dfs(arr, i + 1, j - 1);
        }
        return -1;
    }
}
